package practice;

import java.security.Key;
import java.util.*;

public class Day38 {
    //最小路径和
    public int minPathSum(int[][] grid) {
        int n = grid.length;
        int m = grid[0].length;
        int[][] dp = new int[n+1][m+1];
        for(int i = 2; i <= n; i++) {
            dp[i][0] = Integer.MAX_VALUE;
        }
        for(int j = 2; j <= m; j++) {
            dp[0][j] = Integer.MAX_VALUE;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= m; j++) {
                dp[i][j] = grid[i-1][j-1] + Math.min(dp[i-1][j],dp[i][j-1]);
            }
        }
        return dp[n][m];
    }
    //单词拆分
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean[] dp = new boolean[n+1];
        Set<String> set = new HashSet<>();
        for(String str : wordDict) {
            set.add(str);
        }
        s = " " + s;
        dp[0] = true;
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= i; j++) {
                dp[i] = set.contains(s.substring(j,i+1)) && dp[j-1];
                if(dp[i]) {
                    break;
                }
            }
        }
        return dp[n];
    }

    public int firstMissingPositive(int[] nums) {
        //置换
        int n = nums.length;
        //将所有负数换成n+1
        for(int i = 0; i < n; i++) {
            if(nums[i] <= 0) {
                nums[i] = n+1;
            }
        }
        for(int i = 0; i < n; i++) {
            int num = Math.abs(nums[i]);
            if(num <= n && num-1 >= 0) {
                nums[num-1] = -Math.abs(nums[num-1]);
            }
        }
        for(int i = 0; i < n; i++) {
            if(nums[i] > 0) {
                return i+1;
            }
        }
        return n+1;
    }
    //跳跃游戏
    public int jump(int[] nums) {
        int left = 0;
        int right = 0;
        int max = 0;
        int ret = 0;
        if(nums.length == 1) {
            return 0;
        }
        while(left <= right) {
            for(int i = left; i <= right; i++) {
                max = Math.max(i+nums[i],max);
            }
            ret++;
            if(max >= nums.length-1) {
                return ret;
            }
            //right是上一个元素能跳到的最后一个位置
            left = right+1;
            right = max;
        }
        return 0;
    }
    //和为k的子数组
    public int subarraySum(int[] nums, int k) {
        Map<Integer,Integer> map = new HashMap<>();
        int sum = 0;
        map.put(0,1);
        int count = 0;
        for(int x : nums) {
            count += x;
            sum += map.getOrDefault(count-k,0);
            map.put(count,map.getOrDefault(count,0)+1);
        }
        return sum;
    }

    //翻转链表2
    public ListNode reverseBetween(ListNode head, int left, int right) {
        ListNode newHead = new ListNode(-1);
        newHead.next = head;

        //首先移动到left位置，并且记录前一个位置
        ListNode pre = newHead;
        for(int i = 0; i < left-1; i++) {
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode curNext = head;
        for(int i = 0; i < right-left; i++) {
            curNext = cur.next;
            cur.next = curNext.next;
            curNext.next = pre.next;
            pre.next = curNext;
        }
        return newHead.next;
    }
    //盛水最多的容器
    public int maxArea(int[] nums) {
        int n = nums.length;
        int left = 0;
        int right = n-1;
        int max = 0;
        while(left < right) {
            int count = Math.min(nums[left],nums[right]) * (right - left);
            if(nums[left] < nums[right]) {
                left++;
            }else {
                right--;
            }
            max = Math.max(max,count);
        }
        return max;
    }
    //部分-翻转链表2
    public ListNode reverseBetween1(ListNode head, int left, int right) {
        //首先找到left节点，并且记录前一个节点
        ListNode newHead = new ListNode(1);
        newHead.next = head;
        ListNode prev = newHead;
        for(int i = 0; i < left-1; i++) {
            prev = prev.next;
        }
        //cur是我们要反转的第一个节点
        ListNode cur = prev.next;
        ListNode curNext = null;
        for(int i = left; i < right; i++) {
            curNext = cur.next;
            cur.next = curNext.next;
            curNext.next = prev.next;
            prev.next = curNext;
        }
        return newHead.next;
    }
    //压缩字符串
    public int compress(char[] chars) {
        int left = 0;
        int right = 0;
        int num = 1;
        int n = chars.length;
        while(right < n) {
            while(right+1 < n && chars[right] == chars[right+1]) {
                num++;
                right++;
            }
            chars[left] = chars[right];
            if(num > 1) {
                StringBuilder str = new StringBuilder();
                while(num != 0) {
                    int a = num % 10;
                    str.append(a);
                    num /= 10;
                }
                for(char ch : str.reverse().toString().toCharArray()) {
                    chars[++left] = ch;
                }
            }
            left++;
            right++;
            num = 1;
        }
        return left;

    }
    //合并区间
    public int[][] merge(int[][] intervals) {
        //首先将intervals中的每一个数组按照第一个元素进行升序排序
        Arrays.sort(intervals,(o1,o2)->{
            return o1[0] - o2[0];
        });
        Stack<int[]> stack = new Stack<>();
        stack.push(intervals[0]);
        int k = 1;
        while(!stack.isEmpty() && k < intervals.length) {
            int[] top = stack.peek();
            if(top[1] >= intervals[k][0]) {
                stack.pop();
                //合并
                stack.push(new int[]{top[0],Math.max(top[1],intervals[k][1])});
            }else {
                stack.push(intervals[k]);
            }
            k++;
        }
        int i = 0;
        int[][] ret = new int[stack.size()][2];
        while(!stack.isEmpty()) {
            ret[i++] = stack.pop();
        }
        return ret;
    }
    //将二叉树转换成链表
    public void flatten(TreeNode root) {
        TreeNode cur = root;
        while(cur != null) {
            //先把右子树放到左子树最右边节点
            if(cur.left != null) {
                TreeNode prev = cur.left;
                TreeNode node = prev;
                while(node.right != null) {
                    node = node.right;
                }
                node.right = cur.right;
                cur.right = prev;
                cur.left = null;
            }
            cur = cur.right;
        }
    }
    //全排列
    List<List<Integer>> ret = new ArrayList<>();
    boolean[] flag;
    public List<List<Integer>> permute(int[] nums) {
        if(nums == null || nums.length == 0) {
            return ret;
        }
        flag = new boolean[nums.length];
        dfs(nums,0);
        return ret;
    }
    List<Integer> list = new ArrayList<>();

    private void dfs(int[] nums,int pos) {
        if(pos >= nums.length) {
            ret.add(new ArrayList<>(list));
            return;
        }
        for(int i = 0; i < nums.length; i++) {
            if(!flag[i]) {
                list.add(nums[i]);
                flag[i] = true;
                dfs(nums,pos+1);
                list.remove(list.size()-1);
                flag[i] = false;
            }
        }
    }
}
